|
In computability theory, Rice's theorem states that, for any non-trivial property of partial functions, no general and effective method can decide whether an algorithm computes a partial function with that property. Here, a property of partial functions is called ''trivial'' if it holds for all partial computable functions or for none, and an effective decision method is called ''general'' if it decides correctly for every algorithm. The theorem is named after Henry Gordon Rice, and is also known as the Rice–Myhill–Shapiro theorem after Rice, John Myhill, and Norman Shapiro. ==Introduction== Another way of stating Rice's theorem that is more useful in computability theory follows. Let ''S'' be a set of languages that is nontrivial, meaning # there exists a Turing machine that recognizes a language in ''S'' # there exists a Turing machine that recognizes a language not in ''S'' Then, it is undecidable to determine whether the language recognized by an arbitrary Turing machine lies in ''S''. In practice, this means that there is no machine that can always decide whether the language of a given Turing machine has a particular nontrivial property. Special cases include the undecidability of whether a Turing machine accepts a particular string, whether a Turing machine recognizes a particular recognizable language, and whether the language recognized by a Turing machine could be recognized by a nontrivial simpler machine, such as a finite automaton. It is important to note that Rice's theorem does not say anything about those properties of machines or programs that are not also properties of functions and languages. For example, whether a machine runs for more than 100 steps on some input is a decidable property, even though it is non-trivial. Implementing exactly the same language, two different machines might require a different number of steps to recognize the same input. Similarly, whether a machine has more than 5 states is a decidable property of the machine, as the number of states can simply be counted. Where a property is of the kind that either of the two machines may or may not have it, while still implementing exactly the same language, the property is of the machines and not of the language, and Rice's Theorem does not apply. Using Rogers' characterization of acceptable programming systems, Rice's Theorem may essentially be generalized from Turing machines to most computer programming languages: there exists no automatic method that decides with generality non-trivial questions on the behavior of computer programs. As an example, consider the following variant of the halting problem. Let ''P'' be the following property of partial functions F of one argument: ''P''(F) means that F is defined for the argument '1'. It is obviously non-trivial, since there are partial functions that are defined at 1, and others that are undefined at 1. The ''1-halting problem'' is the problem of deciding of any algorithm whether it defines a function with this property, i.e., whether the algorithm halts on input 1. By Rice's theorem, the 1-halting problem is undecidable. Similarly the question of whether a Turing machine ''T'' terminates on an initially empty tape (rather than with an initial word ''w'' given as second argument in addition to a description of ''T'', as in the full halting problem) is still undecidable. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Rice's theorem」の詳細全文を読む スポンサード リンク
|